n=100;
m=800;
k=100;
D=[9,5,3,10,10,8,4,5,8,10,8,6,3,6,1,10,2,1,3,2,8,2,9,7,2,1,4,4,9,9,9,5,7,3,1,4,7,8,10,9,5,6,6,4,8,3,2,4,7,5,9,2,1,10,4,3,3,9,5,2,8,6,3,7,2,4,8,3,1,5,4,5,5,7,8,7,7,8,1,8,7,8,10,3,5,6,9,1,3,9,7,5,7,1,2,1,3,5,2];
T=[2,93,401,42,60,50,11,149,225,8,69,333,53,1,12,28,284,43,338,1,628,132,31,1,46,77,43,76,129,560,11,2,1,53,19,51,44,70,15,448,189,8,65,1,259,2,23,166,56,43,216,8,31,134,17,37,45,7,146,208,478,12,1,40,272,42,372,30,75,1,19,129,1,1,126,21,302,463,188,14,1,82,1,48,329,26,220,117,186,1,422,244,214,81,143,220,1,27,89,223,24,1,117,6,12,22,12,290,315,7,49,1,229,79,1,162,1,204,20,467,2,54,19,236,108,113,19,13,33,266,39,82,10,3,67,11,58,19,73,75,181,57,19,29,42,120,21,1,65,103,121,97,233,52,1,54,80,88,8,96,9,260,97,175,461,19,22,9,8,657,6,370,108,212,144,260,20,334,661,90,101,106,2,190,60,77,43,252,43,19,66,57,10,1,85,213,484,166,68,1,49,1,141,112,14,195,10,1,28,439,58,115,30,94,150,4,57,36,1,848,36,67,1,155,58,69,252,148,11,241,1,297,35,211,377,123,45,191,86,6,10,89,668,9,212,9,58,188,141,60,63,8,157,27,27,33,13,109,16,115,1,110,99,308,6,51,3,235,32,5,25,3,4,151,63,1,164,63,139,22,63,37,93,2,23,387,109,48,70,24,52,258,270,1,384,444,1,320,2,31,93,105,198,194,72,43,11,19,2,116,13,108,1,63,87,161,111,297,142,112,245,44,19,91,425,393,26,20,33,189,76,109,30,1,81,15,54,15,56,73,1,57,22,432,6,47,5,8,391,16,83,153,156,74,97,194,1,131,13,88,335,45,155,430,198,4,1,12,133,10,62,413,156,2,41,5,9,176,13,85,161,252,6,64,37,40,12,9,163,22,88,3,22,45,139,46,3,1,295,23,22,6,9,74,127,21,399,89,163,166,392,41,63,20,160,22,134,233,249,9,451,35,21,1,146,40,24,6,3,8,45,135,237,39,376,655,106,1,256,1,61,33,17,103,104,414,185,266,381,4,579,223,10,80,15,158,141,426,71,1,9,46,163,67,228,281,86,226,1,95,244,5,218,13,216,111,377,3,191,1,10,197,1,268,362,48,76,1,25,229,482,175,114,4,18,4,1,17,221,26,11,26,108,45,24,57,60,89,105,9,140,121,1,53,117,183,36,181,2,290,8,78,598,78,11,1,127,342,97,20,25,49,178,57,90,220,33,399,262,294,181,1,98,22,26,470,1,215,3,1,38,52,26,1,3,9,33,85,310,242,75,29,54,48,46,106,91,213,44,17,19,144,44,10,46,239,21,113,172,260,47,51,343,210,401,36,134,17,46,115,1,117,61,6,228,33,26,23,98,12,3,1,44,84,22,27,201,1,160,21,3,68,7,19,108,4,148,149,1,271,35,18,86,25,6,125,79,3,19,309,90,226,18,13,1,20,85,70,81,7,40,305,374,21,6,20,2,103,16,41,1,41,60,75,128,26,244,239,16,178,170,119,225,7,110,148,222,509,456,24,1,1,18,81,211,114,1,139,2,348,36,57,3,90,34,143,87,24,32,192,542,177,104,11,1,1,387,443,121,20,15,65,1,381,2,131,56,357,10,212,159,34,22,94,360,6,1,8,19,230,4,80,34,125,213,210,170,60,576,9,133,1,65,8,100,183,10,55,96,18,46,62,83,13,145,180,1,52,11,295,15,467,1,20,48,43,17,232,29,19,153,34,344,361,27,268,1,93,124,40,1,121,2,256,10,6,62,2,8,74,59,5,38,3,20,23,17,1,358,132,97,16,133,249,116,73,153,4,17,40];
A=[3,14,41,11,10,47,2,24,47,5,15,38,47,1,7,17,32,7,36,2,64,42,11,1,26,32,69,11,39,80,2,3,1,9,3,10,8,14,5,53,71,4,30,42,72,7,14,61,39,9,25,6,7,37,5,11,46,3,29,30,52,15,1,5,38,60,42,29,30,1,17,27,1,1,25,3,82,56,52,3,13,13,1,10,56,4,27,15,33,1,47,78,26,23,18,42,1,5,10,40,7,1,14,2,3,6,4,31,41,2,33,1,49,13,1,26,1,25,3,53,3,27,3,93,59,13,3,13,12,41,14,11,2,3,44,5,18,9,10,10,35,8,13,23,12,31,6,1,8,30,14,19,84,11,1,8,69,12,2,42,7,36,20,37,59,6,16,6,53,89,18,53,20,46,33,38,5,39,79,25,24,36,5,71,31,19,7,64,7,6,38,32,37,1,56,33,62,27,11,1,6,1,40,14,8,34,20,1,15,61,11,33,15,12,29,23,18,12,1,89,38,11,1,26,10,23,44,17,15,64,1,54,5,54,80,22,27,20,73,7,2,14,72,23,39,2,13,25,35,12,25,5,19,10,8,38,30,19,23,40,28,60,11,36,2,21,9,44,17,14,54,17,3,32,11,1,41,27,32,10,10,8,11,11,7,66,33,14,14,11,7,70,38,1,54,80,1,35,2,4,13,67,37,22,17,11,3,8,2,54,3,37,1,13,11,32,56,35,30,31,43,12,6,23,67,46,14,3,15,20,12,40,8,1,18,3,7,6,9,13,7,11,5,47,5,20,13,22,50,7,22,19,19,19,23,37,3,39,3,15,44,9,95,48,88,46,1,3,35,2,14,49,23,3,38,32,3,50,5,20,52,37,4,9,11,9,6,2,20,5,10,7,5,13,50,15,6,1,36,5,4,23,4,43,20,5,45,36,33,21,46,15,8,4,17,14,47,38,64,5,46,6,17,1,73,8,15,36,2,6,7,16,37,6,53,94,36,7,78,1,54,5,5,13,12,47,21,56,67,2,64,29,34,11,7,35,20,45,9,1,3,16,63,35,63,30,75,37,1,14,27,2,64,3,30,15,43,2,35,1,6,57,1,41,38,10,15,1,4,54,64,23,20,2,9,3,1,6,24,15,56,6,15,49,4,10,11,13,78,44,48,74,1,16,53,20,5,54,2,36,3,10,67,10,2,1,15,70,53,3,8,10,32,7,12,26,7,58,33,36,28,1,36,33,5,50,1,58,12,1,44,25,10,1,6,3,9,45,38,30,55,8,8,30,6,17,11,25,6,13,20,22,8,9,8,88,6,29,25,48,23,8,82,36,45,6,25,6,19,37,1,20,16,7,39,5,4,7,26,5,5,1,6,11,5,17,66,1,32,8,6,10,2,7,75,2,22,52,1,43,12,4,21,7,4,45,11,2,3,37,17,53,3,55,1,6,64,20,15,6,5,64,85,11,3,23,2,14,30,9,1,10,73,12,38,7,38,42,8,35,27,13,39,2,15,30,39,89,54,6,1,1,4,53,35,23,1,18,12,60,26,16,10,11,10,35,19,5,5,43,70,40,81,2,30,1,48,53,14,4,5,8,1,47,6,50,7,67,2,32,22,5,6,21,56,9,1,3,12,30,3,11,15,25,39,36,53,11,75,5,20,1,21,7,22,25,8,27,12,4,17,14,33,3,19,19,1,11,3,71,3,80,1,12,7,36,4,41,12,3,36,35,67,62,11,37,1,17,32,31,1,27,10,34,2,2,17,3,4,14,27,2,30,6,5,5,3,1,37,16,13,3,22,38,15,9,34,6,7,9];
B=[11,22,73,32,18,68,54,83,88,44,26,57,77,51,9,37,39,9,67,3,86,87,65,5,38,56,99,14,44,100,11,12,87,22,14,15,91,62,23,76,98,9,38,56,80,8,25,68,63,17,55,39,73,66,20,15,68,4,67,81,88,32,16,9,63,84,100,31,41,70,94,41,54,25,82,11,84,63,71,83,38,38,3,16,95,5,56,64,81,6,73,91,47,74,77,55,10,71,43,66,37,2,48,98,10,69,100,97,44,7,42,52,86,83,55,87,2,59,84,90,10,36,5,99,81,16,5,67,29,55,44,84,9,75,83,85,41,87,43,24,81,18,99,66,51,76,26,26,27,45,51,70,93,83,5,23,90,70,11,75,41,63,21,42,96,23,43,7,64,93,50,81,27,72,39,61,34,43,98,51,30,69,10,88,41,23,24,74,72,90,67,51,93,2,82,79,81,88,52,2,78,25,47,80,65,39,38,48,54,87,53,82,84,31,61,36,72,53,34,93,53,90,3,38,46,76,95,24,17,81,31,59,20,64,87,52,31,73,79,16,3,24,73,94,88,3,93,36,47,33,93,12,32,43,23,93,65,36,32,84,34,85,45,94,4,53,12,90,60,23,74,30,9,39,17,15,77,68,94,97,45,9,14,12,99,70,66,96,19,15,11,78,56,48,94,99,2,49,37,9,23,98,55,34,34,78,4,22,6,59,4,66,2,15,19,66,83,78,39,92,48,60,37,77,68,67,78,8,24,26,25,66,24,2,92,15,8,92,27,60,89,23,88,85,15,78,97,23,78,10,95,62,24,50,28,51,27,44,47,39,56,27,97,88,96,87,94,5,84,75,17,87,24,24,82,95,7,86,8,66,69,52,28,32,68,11,13,28,44,15,31,58,18,38,87,45,11,2,83,6,9,26,16,99,40,7,85,46,62,39,92,52,33,5,87,58,84,49,95,30,100,16,51,89,85,28,23,90,51,86,22,31,56,9,73,97,59,83,89,5,83,68,59,27,81,77,95,72,77,3,98,32,99,31,55,96,52,49,10,3,38,55,65,51,69,48,83,49,8,61,28,3,77,11,76,21,76,19,42,6,16,79,2,78,69,73,49,13,10,88,86,44,81,20,23,4,2,8,84,59,66,11,73,58,32,77,27,31,82,62,99,80,3,20,69,32,28,88,13,74,54,16,77,58,4,2,23,100,66,36,81,36,62,20,31,28,17,79,44,54,64,19,72,40,38,94,52,79,48,11,94,46,36,13,74,10,62,95,97,52,100,27,50,53,61,45,20,29,22,25,24,89,12,27,12,94,41,51,28,100,91,84,96,50,55,19,68,31,76,58,68,31,36,66,60,69,34,8,43,6,20,3,34,29,11,31,78,19,37,100,13,25,91,14,90,5,71,63,2,87,21,5,38,93,5,63,28,16,73,95,73,73,75,71,4,14,83,37,28,17,6,69,97,30,14,79,3,56,57,12,6,11,82,16,51,21,86,85,91,80,75,21,83,5,33,47,58,95,95,66,8,31,38,63,43,68,20,80,38,69,30,21,48,15,22,93,70,17,72,68,91,81,90,12,92,12,85,63,70,99,39,10,19,61,26,73,13,81,76,41,27,12,91,36,71,12,22,31,16,72,4,76,39,64,44,42,84,28,97,33,92,2,24,55,36,47,48,35,73,11,28,92,63,4,20,88,2,69,12,91,42,81,9,43,13,71,13,58,34,39,56,53,74,70,71,74,3,55,36,86,65,42,18,61,4,29,29,25,11,17,52,46,84,81,89,18,32,7,94,25,42,16,29,40,29,40,54,54,18,42];